// 47.[DFS递归含重复swap] 全排列 II
// https://leetcode.cn/problems/permutations-ii/
// https://www.cnblogs.com/grandyang/p/4359825.html
//给定一个可包含重复数字的序列 nums, [-10,10]按任意顺序 返回所有不重复的全排列。
//输入：nums = [1,1,2]
//输出：
//[[1,1,2],
// [1,2,1],
// [2,1,1]]
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
#include <bits/stdc++.h>
using namespace std;
#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif
class Solution {
  //  1,2,3,3,3,4,4,4
  //  考虑idx是否加入path
  void dfs(int idx) {
    if (idx == nums_.size()) {
      res_.push_back(path);
      return;
    }
    set<int> record;
    for (size_t i = idx; i < nums_.size(); i++) {
      if (record.find(nums_[i]) != record.end()) continue;
      record.insert(nums_[i]);
      swap(nums_[i], nums_[idx]);
      dfs(idx + 1, path);
      swap(nums_[i], nums_[idx]);
    }
  }
  vector<int> nums_;
  vector<int> vtVisited_;
  vector<vector<int>> res_;

 public:
  vector<vector<int>> permuteUnique(vector<int> nums) {
    nums_ = nums;
    dfs(0);
    return res_;
  }
};
int main() {
  Solution sol;
  vector<vector<int>> out = sol.permuteUnique({1, 2, 3, 3});
  for (auto vt : out) {
    for (auto n : vt) PF("%d,", n);
    PF("\n");
  }
  return 0;
}